package com.mamingchao.foundation.arraysort.quicksort;

/**
 * 快速排序--》 双轴快排
 * 1 4 6 9 10  2 3 5 8 7
 * 经典的快速排序，是单轴快排；选定一个轴，比轴大的放到右边；比轴小的放在左边
 * 左边和右边同时 遍历；左边遍历到 大于轴的 和 右边遍历到小于轴的，两个值交换
 *
 * 哈哈，我发现了一个bug；把7改成10，就会一直循环
 * Created by mamingchao on 2021/3/12.
 */
public class QuickSort {
    public static void main(String[] args) {

        int[] arr = {1,4,6,9,10,2,3,5,8,7};
//        int[] arr = {1,4,6,9,7,2,3,5,8,10};
//        int[] arr = {1,3,4};
        sort1(arr,0,9);
        printArr(arr);

    }

    /**
     * 这个版本想的太复杂了
     *
     * @param arr 待排序原数组
     * @param left 原数组需要 快排的子数组第一个元素 索引位置
     * @param right 原数组需要 快排的子数组最后一个元素 索引位置
     */
    private static void sort(int[] arr,int left,int right) {

        if (left >= right) return;

        int pivot = left + (right-left) / 2;
        //
        int i = left;
        //从右向左遍历的索引
        int j = right;


        //遍历，当 i == j 的时候，停止
        while(i < pivot && j > pivot) {

            //在小于等于 pivot 的索引范围内，找到 比轴值大的那个索引；如果没有，就跟pivot指同一个位置
            while (arr[i] < arr[pivot] && i < pivot) {
                i++;
            }
            //在大于等于 pivot 的索引范围内，找到 比轴值小的那个索引；如果没有，就跟pivot指同一个位置
            while (arr[j] > arr[pivot] && j > pivot) {
                j--;
            }

            if (i != pivot && j != pivot) {
                swap(arr,i,j);
                j--;
                i++;
            }else if (i == pivot && j > pivot) {
                swap(arr,pivot,j);
            } else if (j == pivot && i < pivot) {
                swap(arr,pivot,i);
            }
        }

        sort(arr,left,pivot-1);
        sort(arr,pivot+1,right);
    }


    /**
     *
     * 这是自己实现的最初版本
     * 这个版本已经接近成功，但是 败笔就是 随机设置了轴，这样 轴的值 影响了 i 和j 的遍历判断
     * @param arr 待排序原数组
     * @param left 原数组需要 快排的子数组第一个元素 索引位置
     * @param right 原数组需要 快排的子数组最后一个元素 索引位置
     */
    private static void sort1(int[] arr,int left,int right) {

        if (left == right) return;

        int pivot = left + (right-left) / 2;
        //从左向右遍历的索引
        int i = left;
        //从右向左遍历的索引
        int j = right;

        while(i < j) {

            while (arr[i] < arr[pivot]) {
                i++;
            }

            while (arr[j] > arr[pivot]) {
                j--;
            }

            swap(arr,i,j);
        }
        //当i == j 的时候
        swap(arr,i,pivot);
        sort(arr,left,pivot-1);
        sort(arr,pivot+1,right);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
